package org.datamining.guha.model.node.iterative;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

import org.datamining.guha.model.literal.Literal;
import org.datamining.guha.model.node.AbstractNode;
import org.datamining.guha.model.node.Node;

/**
 * This implementation of Node uses iterative algorithm of tree traversal in
 * some methods. This should save some stack memory and could bring advantage
 * when the tree is big. However, we had to define another variable in each node
 * which is used during iterative traversal.
 * <p>
 * In the future we need to evaluate / worry about two things:
 * <ul>
 * <li>Does this implementation really bring memory savings? (We should have
 * savings in stack but we have one additional variable in each Node).
 * <li>It will be probably very difficult to make this implementation thread
 * safe.
 * </ul>
 * 
 * @author Lukas Vlcek
 * 
 */
public class IterativeNode extends AbstractNode {

	// private static Log log = LogFactory.getLog(IterativeNode.class);

	/**
	 * succpos must be always in range <0, successors.size()> It is used for
	 * interative tree traversal.
	 */
	private int succpos;

	/**
	 * Creates a new instance of IterativeNode with specified Literal,
	 * nextLitaralNode, previousLiteralNode and empty succesors List.
	 */
	public IterativeNode(Literal l, Node nextLitaralNode,
			Node previousLiteralNode, long frequency) {
		this.literal = l;
		this.frequency = frequency;
		this.successors = new LinkedList<Node>();
		this.succpos = -1;
		this.parent = null;
		this.nextLiteralNode = nextLitaralNode;
		this.previousLiteralNode = previousLiteralNode;
	}

	/**
	 * Creates a new instance of IterativeNode with specified Literal, parent
	 * node, nextLitaralNode, previousLiteralNode and empty succesors List.
	 */
	public IterativeNode(Literal l, Node parent, Node nextLitaralNode,
			Node previousLiteralNode, long frequency) {
		this.literal = l;
		this.frequency = frequency;
		this.successors = new LinkedList<Node>();
		this.succpos = -1;
		this.parent = parent;
		this.nextLiteralNode = nextLitaralNode;
		this.previousLiteralNode = previousLiteralNode;
	}

    /**
     * Performs setup of internal position variable <code>succpos</code> which
	 * is used for iterative tree traversal.
     */
    public Node getLastSuccessor() {
    	
        succpos = successors.size();
        if (succpos > 0) return (Node)successors.get(--succpos);
        return null;
        
    }
    /**
     * This method is used for iteration over all successors. IMPORTANT:
	 * getLastSuccessor() method must be called before first call to
	 * getPreviousSuccessor() because setup of internal position variable
	 * <code>succpos</code> is done there.
     */
    public Node getPreviousSuccessor() {
    	
        if (succpos > 0) return (Node)successors.get(--succpos);
        return null;
        
    }
    
    /**
     * @return List of all Nodes with specified Literal
     * from tree represented by this Node.
     *
     * If there are no childs with given Literal then null
     * is returned instead of empty List. We save creation
     * of one object this way.
     */
    @Override
    public List<Node> getNodesWithLiteral(Literal l) {

        List<Node> result = null;
        
        Node n = this;
        Node succ = n.getLastSuccessor();
        
        while (n != null) {
            
            if (n.getLiteral() == l) {
                // Node found
                if (result == null) {
                	// TODO get Array from pool
                	result = new ArrayList<Node>();
                }
                result.add(n);
                // root?
                if (n == this) {
                    n = null;
                    break;
                }
                // get neighbour
                succ = n.getParent().getPreviousSuccessor();
                // if not neighbour then get parent
                if (succ == null) {
                    n = n.getParent();
                } else {
                    n = succ;
                }
                continue;
            }
            
            if (succ != null) {
                n = succ;
                succ = n.getLastSuccessor();
            } else {
                if (n == this) {
                    n = null;
                    break;
                }
                // get neighbour
                succ = n.getParent().getPreviousSuccessor();
                if (succ == null) {
                    n = n.getParent();
                    if (n == this) {
                        n = null;
                    }
                } else {
                    n = succ;
                    succ = n.getLastSuccessor();
                }
            }
        }
        return result;
    }
    
    @Override
    public List<Node> getLastChilds() {
    	
        // TODO get ArrayList from pool
        List<Node> lastChilds = new ArrayList<Node>();
        
        Node n = this;
        while (n != null) {

            // Move down to last child
            Node succ = n.getLastSuccessor();
            if (succ != null) {
                n = succ;
                continue;
            } else {
                // We have reached end of branch
                lastChilds.add(n);
            }
            
            // No child nodes, so walk tree
            while (n != null) {
                
                if (!n.isRoot()) {
                    // Move to sibling if possible.
                    succ = n.getParent().getPreviousSuccessor();
                } else {
                    n = null;
                    break;
                }
                if (succ != null) {
                    n = succ;
                    break;
                }
                
                // Move up
                if (n == this)
                    n = null;
                else
                    n = n.getParent();
                }
            }

        return lastChilds;
    }
}
